#include <stdio.h> 
#include <stdlib.h>
#define num  8
typedef struct node{
	int data;
	struct node *right,*left;
}HeapNode;

HeapNode * CreatTree(int Data[],HeapNode **Q){
	HeapNode *root=NULL,*newp,*cp;
	int pa=1,front,rear;
	front=rear=0;
	for (int i=1;i<num+1;i++){
		newp=(HeapNode *) malloc (sizeof (HeapNode));
		newp->data=Data[i];
		newp->left=newp->right=NULL;
		if(!root) 
			root=newp;
		else{
			cp=Q[pa];
			if (!cp->left)
				cp->left=newp;
			else {
				cp->right=newp;
				pa++;
			}
		}
		Q[++rear]=newp;
	}
	return root;
}

void Exchange(int *X,int *Y){
	*X^=*Y^=*X^=*Y;
}

void Change(int x,int y){
	x^=y^=x^=y;
}

void AdjustTree(HeapNode *root,HeapNode **Q){
	int rear=num,pa=num/2,flag;
	while (rear>1){
		while (1){
			pa=rear/2;
			flag=0;
			while (pa>0){
				if (Q[pa]->data < Q[pa]->left->data){
					Exchange(&Q[pa]->data,&Q[pa]->left->data);
					flag=1;
				}
				if (Q[pa]->right && Q[pa]->data < Q[pa]->right->data){
					Exchange(&Q[pa]->data,&Q[pa]->right->data);
					flag=1;
				}
				pa--;
			}
			if (flag==0)
				break;
		}
		Exchange(&Q[1]->data,&Q[rear]->data);
		if (rear%2)
			Q[rear/2]->right=NULL;
		else Q[rear]->left=NULL;
		rear--;
	}
}

void AdjustLineQ(int Q[]){
	int rear=num,pa,flag;
	while (rear>1){
		while (1){
			pa=rear/2;
			flag=0;
			while (pa>0){
				if (Q[2*pa]>Q[pa]){
					Exchange(&Q[2*pa],&Q[pa]);
					flag=1;
				}
				if (2*pa+1<=num && Q[2*pa+1]>Q[pa]){
					Exchange(&Q[2*pa+1],&Q[pa]);
					flag=1;
				}
				pa--;
			}
			if (!flag)
				break;
		}
		Exchange(&Q[1],&Q[rear]);
		rear--;
	}
	for (int i=num;i>0;i--)
		printf("%5d",Q[i]);
}


int main(void){
	int Data[num+1]={99999,3,2,5,8,4,7,6,9};
	HeapNode *root;
	HeapNode **Q=(HeapNode **) malloc ((num+1)*sizeof (HeapNode *));
	root=CreatTree(Data,Q);
	AdjustTree(root,Q);
	for (int i=num;i>0;i--)
		printf("%5d",Q[i]->data);
	delete Q;
	//AdjustLineQ(Data);
	return 0;
}
